package primary.tree;

/**
 * @Author Elephas
 * @Date 2022/1/8
 **/

import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
*/
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
    public static TreeNode buildTreeNode(Integer[] elems){
        if(elems.length == 0){
            return null;
        }
        TreeNode[] treeNodes = new TreeNode[elems.length+1];
        for (int i = 0; i < elems.length; i++) {
            if(elems[i] != null)
                treeNodes[i+1] = new TreeNode(elems[i],null,null);
        }
        for (int i = elems.length; i > 1; i--) {
            if(treeNodes[i]!=null){
                if(i%2==0){
                    //左孩子
                    treeNodes[i/2].left = treeNodes[i];
                }else{
                    treeNodes[i/2].right = treeNodes[i];
                }
            }
        }
        return treeNodes[1];
    }

    /*
        抄题解,解法一：双指针，从root开始，p指向左，q指向右，二者方向相反进行遍历.递归实现
     */
    public boolean isSymmetric2(TreeNode root){
        return check2(root,root);
    }
    public boolean check2(TreeNode p,TreeNode q){
        if(p == null && q == null){
            return true;
        }
        if( p == null || q == null){
            return false;
        }
        return p.val == q.val && check2(p.left,q.right) && check2(p.right,q.left);
    }

    /*
        抄题解，解法二： 迭代实现递归
     */
    public boolean isSymmetric3(TreeNode root){
        return check3(root,root);
    }

    public boolean check3(TreeNode p, TreeNode q){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(q);
        queue.offer(p);
        while(!queue.isEmpty()){
            TreeNode u = queue.poll();
            TreeNode v = queue.poll();
            if(u == null && v == null)
                continue;
            if( u == null || v == null || (u.val != v.val)){
                return false;
            }
            queue.offer(u.left);
            queue.offer(v.right);
            queue.offer(u.right);
            queue.offer(v.left);

        }
        return true;
    }


}
